大 O 表示法

实际上，我们可以用三种不同的方式描述算法的运行时。

让我们从快速排序的角度来看一下。快速排序选择一个随机元素作为 “基准（pivot）”，然后交换数组中的值，以使小于基准的元素出现在大于基准的元素之前。这给出了 “部分排序”，然后使用类似的过程递归地对左右两边排序。

最佳情况：如果所有元素都相等，那么快速排序平均将只遍历数组一次。这是 O (N)。（这实际上在某种程度上取决于快速排序的实现。但是，有些实现将在有序数组上非常快地运行。）
最坏的情况：如果我们真的很不幸，选取的基准屡次是数组中的最大元素，该怎么办？（实际上，这很容易发生。如果选择子数组中的第一个元素为基准，并且以相反的顺序对数组进行排序，就会遇到这种情况。）在这种情况下，我们的递归不会将数组分成两半，而是在每一半上递归。它只是将子数组缩小了一个元素。这将退化为 O (N^2) 运行时。
预期情况：尽管如此，通常这些完美或糟糕的情况不会发生。当然，有时基准会非常低或非常高，但不会一次又一次地发生。我们可以期望运行时间为 O (N log N)。

空间复杂度是一个与时间复杂度平行的概念。如果我们需要创建一个大小为 n 的数组，这将需要 O (n) 空间。如果我们需要一个大小为 n x n 的二维数组，则将需要 O (n^2) 空间。

递归调用中的堆栈空间也很重要。例如，这样的代码将占用 O (n) 时间和 O (n) 空间。

java

1 	int sum(int n) { /* Ex 1. */
2 		if (n <= 0) {
3 			return 0;
4 		}
5 		return n + sum(n-1);
6 	}

每个调用都会向堆栈添加一层。

1 sum(4)
2 	-> sum(3)
3 		-> sum(2)
4 			-> sum(1)
5 				-> sum(0)

每个调用都被添加到调用堆栈，并占用实际内存。

Add the Runtimes： O(A + B)

java

1 	for (int a ： arrA) { 
2 		print(a);
3 	}
4
5 	for (int b ： arrB) {
6 		print(b);
7 	}

Multiply the Runtimes： O(A*B)

java

1 	for (int a ： arrA) {
2 		for (int b ： arrB) {
3 			print(a + "," + b);
4 		}
5 	}

当你看到一个问题时，如果问题空间（problem space）中的元素数量每次减半，那么运行时可能就是 O (log N)。

这段代码的运行时间是多少？

java

1 	int f(int n) {
2 		if (n <= 1) {
3 			return 1;
4 		}
5  		return f(n - 1) + f(n - 1);
6 	}

这是一个很平衡的二叉树递归结构所以是 O (2^N)

大 O 表示法 ​